1. Field of the Invention
The present invention relates to a multi-item multi-process lot size scheduling method suitable for generating a production schedule applied to a multi-item multi-process production system which uses a plurality of machines to process items corresponding to a plurality of steps during these steps and in which at least one machine or step enables the items to be switched in connection with setup.
2. Description of the Related Art
In general, with a production system composed of multiple processes and multiple machines, production is commonly carried out by dividing a diversified order into a plurality of items and switching these items. With a production system of this kind, i.e. a multi-item multi-process production system, setup must be carried out for each process and each machine facility every time an item to be processed is switched. This setup requires setup time and a setup cost. However, the setup time may be 0. Both setup time and setup cost depend on the item to be processed. On the other hand, an inventory of items requires a holding cost in proportion to the period of holding. The holding cost depends on the item. Thus, it is necessary to make out an optimal schedule for the whole multi-item multi-process production system which prevents a shortage of items or a delay in delivery, and which minimizes the total cost over a planning horizon. This scheduling is called “multi-item multi-process lot size scheduling”.
This scheduling deals with time optimization problems, in other words, problems to be solved for an optimal control process. As more and more items are produced, the size of their inventory increases. On the other hand, as more and more items are consumed, the size of their inventory decreases. Accordingly, the temporal transition of the inventory must be explicitly tracked for all items over the planning horizon.
Further, with the multi-item multi-process lot size scheduling, a single problem contains a mixture of various heterogeneous decision features. In particular, the mixture includes discrete decision features and continuous decision features. These various heterogeneous features are associated with one another and are thus difficult to separate. It is thus difficult to solve the above scheduling problem. The various decision features contained in the scheduling problem include lot sizing, lot sequencing, lot splitting, dispatching, and a decision for a work-in-process inventory for each item. They also include a decision for repeated processing executed by the same machine. These decision features all vary with time.
However, in the prior art, for example, the lot sizing falls under the category of continuous mathematics on the assumption that it is temporarily invariable. On the other hand, the lot sequencing falls under the category of discrete mathematics.
The problems with the multi-item multi-process lot size scheduling are also multi-dimensional. This is because a single item constitutes at least one dimension. Accordingly, the scheduling problem is a multi-dimensional time optimization problem. In this case, the time and memory capacity required for computations increase explosively unless the scheduling problem is decomposed. Thus, in the prior art, a solution to the scheduling problem is not expected to be found within the range of reasonable time and memory capacity. This is widely known as Bellman's curse of dimensionality as described in Document 1 “Bellman, R.: Adaptive Control Processes: A Guided Tour, Princeton University Press (1961)”.
It is thus contemplated that the various heterogeneous decision features contained in the scheduling problem may be decomposed. However, this decomposition is difficult because these heterogeneous decision features are associated with one another and are thus difficult to separate. Thus, the prior art employs a method of sequentially taking up the heterogeneous decision features and processing each taken-up feature separately.
However, artificial constraints must be imposed on each feature in order to separate a feature of interest from the others, that is, to explicitly deal with the feature of interest. For example, lot sequencing requires the size of each lot to be determined beforehand. Thus, in the prior art, to solve a multi-dimensional time optimization problem containing various heterogeneous decision features, artificial constraints are unavoidably imposed whenever one feature is separated from the others. Consequently, it is difficult to simultaneously optimize all features.